package cn.fansunion.leecode.string;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 859. 亲密字符串<br/>
 * 给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ； 否则返回 false 。<br/>
 * 
 * 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。<br/>
 * 
 * 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。<br/>
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/buddy-strings 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-19
 */
public class BuddStrings {
    /*示例 1：
    
    输入：s = "ab", goal = "ba"
    输出：true
    解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
    示例 2：
    
    输入：s = "ab", goal = "ab"
    输出：false
    解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
    示例 3：
    
    输入：s = "aa", goal = "aa"
    输出：true
    解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
    示例 4：
    
    输入：s = "aaaaaaabc", goal = "aaaaaaacb"
    输出：true
     
    提示：
    
    1 <= s.length, goal.length <= 2 * 104
    s 和 goal 由小写英文字母组成*/
    /**
     * 按照题目意思和定义，正常交换，再比较（时间复杂度：O(N*N)）leecode超时了
     * @param s
     * @param goal
     * @return
     */
    public boolean buddyStrings(String s, String goal) {
        //false的情况
        if(s==null || goal== null) {
            return false;
        }
        if(s.length() != goal.length()) {
            return false;
        }
        //排序后，不相同，也不可能
        char[] charArray1=s.toCharArray();
        char[] charArray2=goal.toCharArray();
        Arrays.sort(charArray1);
        Arrays.sort(charArray2);
        if(!Arrays.equals(charArray1, charArray2)) {
            return false;
        }
        //正常情况，交换一次再比较
        for (int i = 0; i < s.length(); i++) {
            for (int j = 1; j < s.length(); j++) {
                if (i != j) {
                    //产生新的char
                    char[] chars = s.toCharArray();
                    swap(chars, i, j);
                    if (Arrays.equals(chars, goal.toCharArray())) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }
    
    /**
     * 尝试创新解法：用O(n)解法
     * @param s
     * @param goal
     * @return
     */
    public boolean buddyStringsGood(String s, String goal) {
        //false的情况
        if(s==null || goal== null) {
            return false;
        }
        if(s.length() != goal.length()) {
            return false;
        }
        //排序后，不相同，也不可能
        char[] charArray1=s.toCharArray();
        char[] charArray2=goal.toCharArray();
        Arrays.sort(charArray1);
        Arrays.sort(charArray2);
        if(!Arrays.equals(charArray1, charArray2)) {
            return false;
        }
        //不排序，比较2个数组的区别
        int difSize=0;
        //2个字符串，不同字母的索引位置
        int[] difIndex=new int[s.length()];
        for (int index = 0; index < s.length(); index++) {
            if(s.charAt(index)!=goal.charAt(index)) {
                //记录前2次
                difIndex[difSize]=index;
                difSize++;
                //不相同的字符有3次+，肯定不匹配了
                if(difSize>=3) {
                    break;
                }
            }
        }
        //超过2次，达到3次，肯定不行了
        if(difSize>=3) {
            return false;
        }
        //正常的交换情况，得对称
        else if(difSize==2) {
            final int dif0Index = difIndex[0];
            final int dif1Index = difIndex[1];
            if(s.charAt(dif0Index) == goal.charAt(dif1Index) &&s.charAt(dif1Index) == goal.charAt(dif0Index) ) {
                return true;
            }else {
                return false;
            }
        }
        //只有1次，也不行
        else if(difSize==1) {
            return false;
        }
        //aba,abba,aabb,abbc可以；abcd就不行
        //1个字符串，在交换1次之后，仍然完全一样；说明字符串，至少有2个一样的字符
        else if(difSize==0) {
            boolean existSame=existSame(goal);
            if(existSame) {
                return true;
            }else {
                return false;
            }
        }
        return false;
    }

    private boolean existSame(String goal) {
        Set<Character> set = new HashSet<>();
        final char[] charArray = goal.toCharArray();
        for(char ch:charArray) {
            set.add(ch);
        }
        return set.size()!=goal.length();
    }
}
